package com.sali.其他;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 丑数
 */
public class JZ_49 {

    public int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0;
        //要乘的因数
        int[] factors = {2, 3, 5};
        //去重
        HashMap<Long, Integer> mp = new HashMap<>();
        //小顶堆
        PriorityQueue<Long> pq = new PriorityQueue<>();
        //1先进去
        mp.put(1L, 1);
        pq.offer(1L);
        long res = 0;
        for(int i = 0; i < index; i++){
            //每次取最小的
            res = pq.poll();
            for(int j = 0; j < 3; j++){
                //乘上因数
                long next = (long)res * factors[j];
                //只取未出现过的
                if(!mp.containsKey(next)){
                    mp.put(next, 1);
                    pq.offer(next);
                }
            }
        }
        return (int)res;
    }

}
